#pragma once
#include<vector>
#include<iostream>
#include<iterator>
using namespace std;

class Sort
{
private:
	template<class T>
	void privatePrint(vector<T>nums) {
		for (int i = 0; i < nums.size(); i++)
			cout << nums[i] << " ";
		cout << endl;
	}

	template<class T>
	void swap(T &a, T &b)
	{
		a = a + b;
		b = a - b;
		a = a - b;
	}

	template<class T>
	void bubbleSort(vector<T>& nums) {
		int i, j;
		for (i = 0; i < nums.size() - 1; i++) {
			for (j = 0; j < nums.size() - 1 - i; j++) {
				if (nums[j] > nums[j + 1]) {
					Sort::swap(nums[j], nums[j + 1]);
				}
			}
		}
	}

	template<class T>
	void insertSort(vector<T>&nums) {
		for (int i = 1; i < nums.size(); i++) {
			int j = i;
			while (j > 0 && nums[j] < nums[j - 1]) {
				Sort::swap(nums[j], nums[j - 1]);
				j--;
			}
		}
	}

	template<class T>
	void selectSort(vector<T>&nums) {
		for (int i = 0; i < nums.size(); i++) {
			int t = findMinLoc(nums, i);
			if (t != i)
				swap(nums[t], nums[i]);
		}
	}

	template<class T>
	int findMinLoc(vector<T>&nums,int s) {
		int min = nums[s];
		int minLocation = s;
		for (int i = s; i < nums.size(); i++) {
			if (nums[i] < min) {
				min = nums[i];
				minLocation = i;
			}
		}
		return minLocation;
	}

	template<class T>
	T findFather(T son) {
		if (son % 2 == 0)
			return (son / 2 - 1);
		else
			return (son / 2);
	}

	template<class T>
	vector<T> heapSort(vector<T>&nums) {
		vector<T> result;
		int size = nums.size();
		for (int i = 0; i < size; i++) {
			for (int i = nums.size() - 1; i > 0; --i) {
				int father = findFather(i);
				if (nums[i] < nums[father])
					swap(nums[i], nums[father]);
			}
			result.push_back(nums[0]);
			vector<int>::iterator it = nums.begin();
			nums.erase(it);
		}
		return result;
	}

	template<class T>
	int quickSortTempLocation(vector<T>&nums,int left,int right) {
		T temp = nums[left];
		while (left != right) {
			while (nums[right] >= temp && right > left) {
				right--;
			}
			if (left < right) {
				nums[left] = nums[right];
				left++;
			}
			while (nums[left] <= temp && left < right) {
				left++;
			}
			if (left < right) {
				nums[right] = nums[left];
				right--;
			}
		}
		nums[left] = temp;
		return left;
	}

	template<class T>
	void quickSort(vector<T>&nums, int left, int right) {
		if (right <= left)
			return;
		int location = left;
		location = quickSortTempLocation(nums, left, right);
		quickSort(nums, left, location - 1);
		quickSort(nums, location + 1, right);
	}
	

public:
	Sort();
	~Sort();

	vector<int> nums;

	template<class T>
	void PrintVector(vector<T>nums) {
		for (int i = 0; i < nums.size(); i++)
			cout << nums[i] << " ";
		cout << endl;
	}

	template<class T>
	void BubbleSort(vector<T>&nums) {
		bubbleSort(nums);
	}

	template<class T>
	void InsertSort(vector<T>&nums) {
		insertSort(nums);
	}

	template<class T>
	void SelectSort(vector<T>&nums) {
		selectSort(nums);
	}

	template<class T>
	void ShellSort(vector<T>&nums) {

	}

	template<class T>
	void HeapSort(vector<T>&nums) {
		nums = heapSort(nums);
	}

	template<class T>
	void QuickSort(vector<T>&nums) {
		quickSort(nums, 0, nums.size() - 1);
	}
};

